package com.chj.lintcode.backpack;

public class Code08_BackpackVIII {
	/*
	 * Description Give some coins of different value and their quantity. Find how
	 * many values which are in range 1 ~ n can these coins be combined Example
	 * Given: n = 10 value = [1,2,4] amount = [2,1,1] Return: 8 They can combine all
	 * the values in 1 ~ 8 Tags Backpack Dynamic Programming
	 */

	/**
	 * Approach: Multiple Backpack 该题属于多重背包问题。 dp[i][j]表示：在前 i 个元素中，取得价值为 j 的方案是否成立
	 * 因此 dp[i][j] |= dp[i - 1][j - k * value[i]] (j >= k * value[i]) 最后我们只需要统计
	 * dp[n-1][m] 中有几个方案为 true 即可。
	 *
	 * 注意点：题目要求至少取一个值，即全部都不取（结果为0）的方案是不成立的 而我们这里是认为一个都不取的方案是成立的，因此结果需要 减去1.
	 *
	 * 关于 多重背包问题 的详细解析与解法优化可以参考：
	 * https://github.com/cherryljr/LintCode/edit/master/Backpack%20VII.java
	 */
	/**
	 * @param m: the value from 1 - m
	 * @param value: the value of coins
	 * @param amount: the number of coins
	 * @return: how many different value
	 */
	public static int backPackVIII(int m, int[] value, int[] amount) {
		int n = value.length;
		boolean[][] dp = new boolean[n][m + 1];
		// Initialize
		for (int i = 0; i <= amount[0]; i++) {
			if (i * value[0] <= m) {
				dp[0][i * value[0]] = true;
			}
		}

		// Function
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= m; j++) {
				for (int k = 0; k <= amount[i]; k++) {
					if (j >= k * value[i]) {
						dp[i][j] |= dp[i - 1][j - k * value[i]];
					} else {
						// 如果当前价值超过了总价值 j,那么后面就没有继续计算的必要了
						break;
					}
				}
			}
		}

		// Answer
		int rst = 0;
		for (int i = 0; i <= m; i++) {
			if (dp[n - 1][i]) {
				rst++;
			}
		}
		return rst - 1;
	}

//	https://www.jianshu.com/p/26d8dbeacf19
//		VIII
//		给一些不同价值和数量的硬币。找出这些硬币可以组合在1 ~ n范围内的值
//
//		样例
//		Given:
//		n = 10
//		value = [1,2,4]
//		amount = [2,1,1]
//
//		Return: 8
//		They can combine all the values in 1 ~ 8
//
//		作者：想当厨子的程序员
//		链接：https://www.jianshu.com/p/26d8dbeacf19
//		来源：简书
//		著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
	public static void main(String[] args) {
		{
			int m = 10;
			int[] prices = { 1, 2, 4 };
			int[] amounts = { 2, 1, 1 };
			System.out.println(backPackVIII(m, prices, amounts));
		}
	}
}
